package ExpressTwo;

class QueueNode<T>{
    T data;
    QueueNode<T> pre,next;
    QueueNode(T data){
        this.data=data;
    }
}

//双向链表
public class QueueList<T> {
    private QueueNode<T> head,tail;
    private int length=0;

    //增加结点
    void add(T data){
        if(data!=null) {
            if (head == null) {
                head = new QueueNode<>(data);
                head.next = head.pre = null;
                tail = head;
            } else {
                tail.next = new QueueNode<>(data);
                tail.next.pre = tail;
                tail = tail.next;
            }
            length++;
        }
    }
    //获取结点
    T get(int index){
        if(index>=length){
            return null;
        }
        else{
            QueueNode<T> p=head;
            while (index--!=0){
                p=p.next;
            }
            return p.data;
        }
    }
    //头出
    T removeHead(){
        if(head!=null){
            QueueNode<T> p=head;
            if(length==1){
                head.next=head.pre=null;
                head=tail=null;
            }
            else{
                head=head.next;
                head.pre=null;
                p.next=p.pre=null;

            }
            length--;
            return p.data;
        }
        return null;
    }
    //尾出
    T removeTail(){
        if(tail!=null){
            QueueNode<T> p = tail;
            if(length==1) {
                head=tail=null;
            }else{
                tail=tail.pre;
                p.pre=p.next=null;
                tail.next=null;
            }
            length--;
            return p.data;
        }
        return null;
    }
    //移除相同数据
    T remove(T data){
        QueueNode<T> p=head;
        while(p!=null&&p.data!=data){
            p=p.next;
        }
        if(p!=null){
            length--;
            if(p==head){
                head=head.next;
                head.pre=null;
                p.next=p.pre=null;
                return p.data;
            }else if(p==tail){
                tail=tail.pre;
                tail.next=null;
                p.next=p.pre=null;
                return p.data;
            }
            else{
                p.pre.next=p.next;
                p.next.pre=p.pre;
                p.pre=p.next=null;
                return p.data;
            }
        }
        return null;
    }
    //获取长度
    int getLength() {
        return length;
    }

    public static void main(String[] args) {
        QueueList<Integer> list=new QueueList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        System.out.println(list.removeHead());
        System.out.println(list.removeHead());
        System.out.println(list.removeHead());
        System.out.println(list.removeHead());
        System.out.println(list.removeHead());
    }
}
